#include<stdio.h>
#include<stdlib.h>

/*  阿里云的面试题
    两个有序数组取交集
    下面的4种写法总体差不多
    都是将较小数的指针向前移动，再进行比较
    f1：用for + 数组的个数进行总体的控制，每次比较一次，移动一次
    f2：以第二个数组的当前数作为基准，每次将第一个数组中的数字连续移动
    f3：f2加强版，两个指针都可以连续移动
    f4：只是为了验证虽然将指针操作写得很难懂，但也是可以工作的

    此问题还需要注意的问题：
        对m、n长度的判断，根据大小和比较选择不同性能的算法
        初步判断，A中的最大值，最小值与B中的首尾值进行比较
        长度相差比较大时，可以用高效的查找算法
        如果内存无法放满，可以参考大数据量处理的方法
*/

void f1(int A[],int B[],int m,int n)
{
    int i,j;
    for(i=0,j=0;i<m && j<m;)
    {
        if(A[i]==B[j])
        {
            printf("%d\n",A[i]);
            i++;j++;
        }
        else if(A[i]<B[j])
        {
            i++;
        }
        else
        {
            j++;
        }
        printf("-----\n");
    }
}

void f2(int A[],int B[],int m,int n)
{
    int *p1,*p2;
    p1=A;p2=B;
    while(p1-A<m && p2-B<n)
    {
        while(*p1<*p2)
        {
            p1++;
        }
        if(*p1==*p2)
        {
            printf("%d\n",*p1);
            p1++;p2++;
        }
        else
        {
            p2++;
        }
        printf("-----\n");
    }
}

void f3(int A[],int B[],int m,int n)
{
    int *p1,*p2;
    p1=A;p2=B;
    while(p1-A<m && p2-B<n)
    {
        while(*p1<*p2)
        {
            p1++;
        }
        if(*p1==*p2)
        {
            printf("%d\n",*p1);
            p1++;p2++;
        }
        while(*p2<*p1)
        {
            p2++;
        }
        printf("-----\n");
    }
}

void f4(int A[],int B[],int m,int n)
{
    int *p1,*p2;
    p1=A;p2=B;
    while(p1-A<m && p2-B<n)
    {
        //: 这样写相对于f2，比较难理解，增加了不必要的思考
        //：完全没有意义，每次倒退一个，最坏情况下，会退O（n）
        //：狗尾续貂的解法
        while(*p1++<*p2);
        p1--;
        //:end

        if(*p1==*p2)
        {
            printf("%d\n",*p1);
            p1++;p2++;
        }
        else
        {
            p2++;
        }
        printf("-----\n");
    }
}

int main()
{
    int A[]={1,3,6,7,9,14,56,400};
    int B[]={6,9,56,100,108,356};
    printf("\nf1\n");
    f1(A,B,8,6);
    printf("\nf2\n");
    f2(A,B,8,6);
    printf("\nf3\n");
    f3(A,B,8,6);
    printf("\nf4\n");
    f4(A,B,8,6);
    return 0;
}
